1. Field of the Invention
The present invention relates to an encryption operating apparatus that encrypts and decrypts data.
2. Description of the Related Art
As a technique of encryption or digital signature of message, a public key cryptography is used. Although the public key cryptography has a larger amount of operation than common key cryptography, when transmitting and receiving the enciphered message, there is an advantage that it is not necessary to share a key. Therefore, the public key cryptography is widely used and various methods are proposed, such as RSA cryptography, Rabin cryptography, ElGamal cryptography, and Elliptic curve cryptography.
In the public key cryptography, a user has a pair of cryptographic keys, a public key and a private key. A public key is widely distributed, while a private key is kept secret. For example, when a user A wishes to transmit a secret message to a user B, the user A encrypts the message using a public key of the user B, and transmits the encrypted message to the user B. The user B receives the encrypted message and can decrypt the encrypted message using an own private key corresponding to the public key. When the user A transmits a message to the user B by adding a digital signature to the message using an own secret key, the user B receives the message and verifies the added digital signature using the public key of the user A, thereby authenticating that the communication party is the user A.
According to an RSA encryption system, n(=pq) is generated from two distinct large random prime numbers p and q, and e is obtained to set a relationship of gcd(e,lcm(p−1, q−1))=1, where gcd is the greatest common divisor and lcm is the least common multiple. The system calculates d=e−1 mod(lcm(p−1, q−1)), and sets e and n as public keys, and sets d as a private key. To decrypt the encrypted message or to sign a message using a private key, the Chinese Remainder Theorem (CRT) is generally used as a high-speed method of modular exponentiation. The CRT is explained below taking an example of a method of generating a signature S=Md modn for a message M.
Because a person who generates a digital signature knows two distinct large prime numbers p and q of n=pq, the person can calculate in advance values of the following equations (1) to (3).dp=d mod(p−1)  (1)dq=d mod(q−1)  (2)a=q−1 mod p  (3)
When a message to be added with a signature is M, a signature S is generated by sequentially calculating the following relational equations (4) to (6).Mp=M mod p, Mq=M mod q  (4)Sp=Mpdp mod p, Sq=Mddq mod q  (5)S=Sq+(a×(Sp−Sq)mod p)×q  (6)
In the above equations (4) to (6), p and q with half a bit length of n are used as modulus of residue number arithmetic. Therefore, it is possible to encrypt or sign about three times faster than calculation using a modulus n.
Although this form allows faster decryption an signing by using CRT, it is less secure since it enable fault-based analysis. The fault-based analysis is an attack method of inducing faults, which means unexpected environmental conditions for example high temperature, unsupported supply voltage or current, excessively high overclocking and etc. to reveal their internal secret data. For instance, an attack method to RSA cryptography using CRT is explained.
By inducing faults, a malfunction occurs during the calculation of Sp in the above equation (5), and the value changes to a wrong value Sp′ (≠Sp). A value S derived from the equation (6) also becomes a wrong value S′ as shown in the following equation (7).S′=Sq+(a×(Sp′−Sq)mod p)×q  (7)
It is clear that a difference between S′ and S is expressed by the following equation (8) and becomes multiples of q. That is, because n=pq, q can be obtained by obtaining a greatest common divisor of S′−S and n (gcd(S′−S, n)=q).S′−S=(a×(Sp′−Sp)mod p)×q  (8)
Conventionally, various techniques have been proposed as measures against the above attack method. For example, JP-A 2005-165290 (KOKAI) discloses the following technique. By calculating C=Se′modn (e′ is an inverse of the modulus p−1 of dp), a check calculation is performed to see whether C is equal to M. When a result of the check calculation is wrong, the calculation result is not output, thereby avoiding the offender from obtaining information containing the secret information.
However, the technique disclosed in JP-A 2005-165290 (KOKAI) has a problem in that modular exponentiation concerning the check process becomes additionally necessary and this takes time, although the technique can cope with a fault-based attack.